package com.alex.program;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,2,1,5,6,4], k = 2
 * 输出：5
 * 示例 2：
 * <p>
 * 输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
 * 输出：4
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= k <= nums.length <= 104
 * -104 <= nums[i] <= 104
 */
public class K大数 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 6};
        int k = 2;
        int kthLargest = findKthLargest(nums, k);
        //System.out.println(kthLargest);
        int i = smallestK(nums, k);
        System.out.println(i);
    }

    /**
     * 若K大是一样的，会输出第一个
     */
    public static int findKthLargest(int[] nums, int k) {
        int[] arr = new int[20001];
        for (int i : nums) {
            // 这样就进行了排序(下标排序了); 其余的数都为0
            arr[i + 10000]++;
        }

        Set<Integer> diffSet = new HashSet<>();
        for (int i = 20000; i >= 0; i--) {
            k -= arr[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return -1;
    }

    /**
     * 若K大是一样的，会输出第一个
     */
    public static int findKthLargestV2(int[] nums, int k) {
        int[] arr = new int[20001];
        for (int i : nums) {
            // 这样就进行了排序(下标排序了); 其余的数都为0
            if (arr[i + 10000] == 0) {
                // 这个保证了 重复的元素, 也只增加一次
                arr[i + 10000]++;
            }
        }

        for (int i = 20000; i >= 0; i--) {
            k -= arr[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return -1;
    }

    public static int smallestK(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; ++i) {
            if (!queue.contains(arr[i]) && queue.peek() < arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        int res = -1;
        for (int i = 0; i < k; ++i) {
            res = queue.poll();
        }

        return res;
    }
}
